package algorithmic_data_structure.堆与堆排序.加强堆;

import org.junit.Test;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class 最大线段重合数 {
    @Test
    public void test(){
        System.out.println(maxCover(new int[][]{
                {1,5},
                {2,4},
                {3,7},
                {4,6},
                {4,9}
        }));
    }
    //给你一些线段，求这些线段中重合的最多数
    static class Line{
        int left;
        int right;
        public Line(int left, int right) {
            this.left = left;
            this.right = right;
        }
    }
    public static int maxCover(int[][] lines){
        int res = 1;
        Line[] allLine = new Line[lines.length];
        for (int i = 0; i < lines.length; i++) {
            allLine[i] = new Line(lines[i][0],lines[i][1]);
        }
        Arrays.sort(allLine,(l1,l2) -> {return l1.left - l2.left;});
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();//默认是小根堆,存放的是线段的右边界
        minHeap.add(allLine[0].right);
        for (int i = 1; i < lines.length; i++) {
            while (!minHeap.isEmpty() && minHeap.peek() <= allLine[i].left){//把最小右边界小于当前线段的左部，说明没有重合，直接弹出
                minHeap.poll();
            }
            minHeap.add(allLine[i].right);
            res = Math.max(res,minHeap.size());
        }
        return res;
    }
    //笨方法
    public static int maxCover1(int[][] lines) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < lines.length; i++) {
            min = Math.min(min, lines[i][0]);
            max = Math.max(max, lines[i][1]);
        }
        int cover = 0;
        for (double p = min + 0.5; p < max; p += 1) {
            int cur = 0;
            for (int i = 0; i < lines.length; i++) {
                if (lines[i][0] < p && lines[i][1] > p) {
                    cur++;
                }
            }
            cover = Math.max(cover, cur);
        }
        return cover;
    }
    // for test
    public static int[][] generateLines(int N, int L, int R) {
        int size = (int) (Math.random() * N) + 1;
        int[][] ans = new int[size][2];
        for (int i = 0; i < size; i++) {
            int a = L + (int) (Math.random() * (R - L + 1));
            int b = L + (int) (Math.random() * (R - L + 1));
            if (a == b) {
                b = a + 1;
            }
            ans[i][0] = Math.min(a, b);
            ans[i][1] = Math.max(a, b);
        }
        return ans;
    }

    public static class StartComparator implements Comparator<Line> {
        @Override
        public int compare(Line o1, Line o2) {
            return o1.left - o2.left;
        }

    }

    public static void main(String[] args) {
        System.out.println("test begin");
        int N = 100;
        int L = 0;
        int R = 200;
        int testTimes = 200000;
        for (int i = 0; i < testTimes; i++) {
            int[][] lines = generateLines(N, L, R);
            int ans1 = maxCover1(lines);
            int ans2 = maxCover(lines);
            if (ans1 != ans2) {
                System.out.println("Oops! --- " + ans1 + " " + ans2);
            }
        }
        System.out.println("test end");
    }
}
